In the art of computer graphics, rendering of a primitive into an image in a three-dimensional graphics system requires a series of transformation steps. Generally, the Host Processor 10, of a system of the type illustrated in FIG. 1, will retrieve information describing the primitive from the System Memory 11 and provide same to the Graphics Subsystem 18. In the Graphics Subsystem, the Geometry Processor will perform a number of operations on the retrieved information in order to convert the information into a three-dimensional computer graphic. Once the geometry operations have been completed, the resulting representation of the image is rasterized in Rasterizer 13 and stored in the Local Memory 14 until it is read out of the Local Memory for display at Display Monitor 15. The series of geometric transformation operations include operations shown in the representative process flow of FIG. 2.
FIG. 2 shows that the original graphic information, described by application 20 in model coordinates, is first transformed into work coordinates via the Model Transformation step 21, whereby transformation matrices are applied to the primitive, thereby transforming it into a unified coordinate system describing the position of all objects in the scene, referred to as world coordinates. At step 22, the primitive's world coordinates are further processed in the View Transformation step to render the image in eye coordinates, as if viewed from a single vantage point with the human eye as the point of origin of the coordinate system.
The eye coordinates are next operated on in a way to add lighting and color to the coordinates, in the Lighting step 23. To this point in the graphics rendering process, all of the operations have simply been done on the Cartesian coordinates. In the Perspective Transformation step 24, the space is transformed into a box, such that the shape of the view volume is transformed to a normalized view volume in which the view plane is located at z=D and the eye at z=O. Perspective coordinates are then mapped into device coordinates in the Perspective Division step 25, yielding device coordinates which can be rasterized for display. The Rasterization processing breaks the display space down into pixels which must be turned on, where image components are present, and pixels which must be turned off, in image background areas.
After converting the image information into device coordinates, it is necessary to clip the image with respect to the view fustrum (i.e., field of view). Clipping is performed as step 26 prior to Rasterization at step 27. FIG. 3 provides a schematic illustration of the view fustrum 30 with several objects inside and outside of its boundaries. Objects, such as 31, which fall completely outside of the view volume are discarded from further processing ("trivial rejection"). Objects, such as 32, which fall entirely within the view volume remain unchanged and are sent directly to the rasterization subsystem ("trivial acceptance"). Objects, 33 and 34, that intersect the boundary of the view volume, however, must be clipped against the view volume boundaries (also known as "clip planes"), such that those objects are split into two portions. Those portions of split or clipped objects which fall without the view volume are discarded, while the portions inside of the view volume are sent to the rasterizer. As is well known in the art, it is most advantageous to perform clipping on triangulated image components. With all vertices of the triangulated image lying in one plane, it is only necessary to know the vertices to perform clipping, without having to operate on each portion of the image volume lying within the vertices.
Clip testing, (i.e., determining whether a triangle can be trivially accepted or rejected) is commonly performed using clip codes for the triangle vertices. Clip codes contain one OUT bit for each clipping plane. The OUT bit is set if the vertex is outside the clipping plane associated with that bit. FIG. 4 shows a two-dimensional example of how clip codes are assigned to different regions formed by the clip planes 41-44. A triangle can be trivially accepted if the bitwise OR of the outcodes of all vertices is 00 . . . 0. A triangle can be trivially rejected if the bitwise AND of the outcodes of all vertices is not 00 . . . 0.
If a triangle cannot be trivially accepted or rejected, it needs to be clipped against the clip planes. A technique frequently used is described in Reentrant Polygon Clipping, Suntherland and Hodgman, CACM, Vol. 17, pages 32-42, (1974). The triangle is clipped successively against each clip boundary. Clipping is performed by determining the intersection of the triangle edges with the boundary. The intersection points with the boundary form new vertices with the clipped triangle(s). If two vertices lie outside of the clipping boundary, only one triangle is produced by the clipping step, as shown for image 50 in FIG. 5A which is clipped to triangle 51 of FIG. 5B. If only one vertex is clipped by the clipping plane, such as is shown for triangle 52 of FIG. 5A, two vertices are produced by the clipping step, shown as polygon 53 of FIG. 5B, which polygon is decomposed into triangles 54 and 55. Clipping of the resulting triangles is then performed with respect to each of the other clipping planes.
FIG. 6 shows a flow diagram describing the steps involved in clipping a triangle. The triangle is provided for processing at step 60, after which the outcodes are computed for all vertices of the triangle, at step 61. If the outcodes indicated that all vertices are outside of the clip planes, then the triangle is trivially rejected at step 62. If not trivially rejected, the determination is made at step 63 as to whether all outcodes are within all clip planes for trivial acceptance of the triangle. For any remaining triangles, clipping is performed at step 64 along a first clip plane, followed by clipping along an adjacent plane, etc.
Assuming a single instruction multiple data (SIMD) computer, where one set of instructions may be applied to different data in parallel by a plurality of the computer engines, the outcode analysis (i.e., comparisons) may be run in parallel on more than one of the SIMD engines. Similarly, once it has been determined by the control processor that clipping is necessary, the computationally intensive clipping steps may be performed in more than one engine at a time. However, to shift from one set of instructions to another (e.g., from outcode assignment to clipping for a single triangle along one plane), where both data and instructions must be retrieved from caches, severely taxes the resources of the SIMD computer, both in computational time and in complexity, even giving rise to invalidation of the contents of the instruction cache necessitating re-loading from main memory. Since the shifting from outcode analysis instruction to clipping instruction may be repeated many times as the contents of an image are evaluated along the six clipping planes, the process becomes unduly long and complex.
What is needed, therefore, is a method for providing clipping of transformed convex polygons along clip planes which can be efficiently and effectively conducted on a SIMD computer.
What is additionally needed is a method for providing clipping of transformed convex polygons along clip planes which maximizes utilization of SIMD engines between instructions.